package com.mdnote.practice.dp;

import javax.swing.plaf.IconUIResource;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/20 0020
 * @description 最长子序和
 */
public class LeetCode53 {


    public static void main(String[] args) {
        LeetCode53 leetCode53 = new LeetCode53();
        int res = leetCode53.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
        System.out.println(res);
    }
    /**
     * 1. 暴力法，两个指针遍历，第一个指针遇到正数停下，移动第二个指针，不断计算最大值  时间复杂度为 平方阶
     * 2. 贪心： 不断求和并记录最大值，如果引入新的元素后值变小了我们就重新开始算  时间复杂度 线性、
     * 3. 分治法：不断求左边 中间 右边的最大值
     * 4. DP 时间复杂度为线性
     *    1. 重复子问题：（左边数组 + 当前数值（ 和 左边数组 谁打
     *    2. DP[i] 表示从0到i个元素最大和
     *    2. DP[i] = DP[I - 1] + Math.max(0, nums[i])  or DP[io] = nums[i] + Math.max(0, dpi - 1[])
     *       前者表示当前最大子序和 = 上一步的子序和 + 这一步的子序和  求出来的是整个序列所有正数之和
     *       后者判断的是当前的数组加上前面序列或者不加前面序列哪个更大
     */
    public int maxSubArray(int[] nums) {
        // greedy
//        return greedy(nums);

        return dp(nums);
    }


    private int dp(int[] nums) {

        int[] dp = new int[nums.length];
        dp[0] = Math.max(0, nums[0]);

        int res = nums[0];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = nums[i] + Math.max(0, dp[i - 1]);
            res = Math.max(res, dp[i]);
        }

        return res;
    }


    private int greedy(int[] nums) {

        int max = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i];
            max = Math.max(count, max);
            if (count < 0) {
                count = 0;
            }
        }
        return max;
    }


}
